//1.双指针-有效三角形的个数

//解法一: 暴力解法: 三层for循环, 任意两边之和 > 第三边
// 优化: 较小的两条边之和 > 第三边
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n = nums.size(), ret = 0;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                for(int k = j + 1; k < n; k++)
                {
                    if(nums[i] + nums[j] > nums[k])
                        ret++;
                }
            }
        }
        return ret;
    }
};


// 解法二: 固定第三边, 使用双指针算法
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ret = 0;
        for(int i = n - 1; i >= 2; i--)
        {
            //双指针
            int l = 0, r = i - 1;
            while(l < r)
            {
                if(nums[l] + nums[r] > nums[i]) 
                {
                    ret += r - l;
                    r--;
                }
                else 
                {
                    l++;
                }
            }
        }
        return ret;
    }
};


//2.双指针-查找和为t的两商品
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int n = price.size();
        int l = 0, r = n - 1;
        while(l < r)
        {
            if(price[l] + price[r] > target) r--;
            else if(price[l] + price[r] < target) l++;
            else return {price[l], price[r]};
        }
        return {-1, -1};
    }
};